package com.algorithm.dp;

/**
 * 最后石块重量ii
 *
 * @author Amadeus
 * @date 2023/10/23
 */
public class lastStoneWeightII {

    public static int lastStoneWeightII(int[] stones) {
        int n = stones.length;
        int sum = 0;
        for (int stone : stones) {
            sum += stone;
        }
        int target = sum / 2;
        int[] dp = new int[target + 1];
        for (int i = 0; i < n; i++) {
            for (int j = target; j >= stones[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        return sum - (2 * dp[target]);
    }

    public static void main(String[] args) {
        System.out.println(lastStoneWeightII(new int[]{31, 26, 33, 21, 40}));
    }

}
